11108. Тавтология

В правильно построенной формуле (ППФ) используются символы K, A, N, C, E, p, q, r, s, t. ППФ называется строка символов, удовлетворяющая условиям:

1. p, q, r, s, t являются ППФ;

2. Если w ППФ, то Nw также является ППФ;

3. Если w и x ППФ, то ППФ будут формулы Kwx, Awx, Cwx, Ewx.

Известно, что:

1. p, q, r, s, t являются логическими переменными, принимающими значения 0 (ложь) и 1 (истина);

2. K, A, N, C, E являются обозначениями логических операций: and, or, not, implies и equals соответственно. Таблицы истинностей функций представлены в таблице:

w	x	Kwx	Awx	Nw	Cwx	Ewx
1	1	1	1	0	1	1
1	0	0	1	0	0	0
0	1	0	1	1	1	0
0	0	0	0	1	1	1

Тавтологией называется ППФ, истинная для всех возможных значений переменных. По заданной ППФ требуется определить, является ли она тавтологией. Например, формула ApNp является тавтологией так как = 1.

Вход. Каждая строка содержит от 1 до 100 символов. Последняя строка содержит 0 и не обрабатывается.

Выход. Для каждой входной ППФ вывести фразу “tautology”, если она является тавтологией и “not” в противном случае.

Пример входа

ApNp

ApNq

0

Пример выхода

tautology

not

РЕШЕНИЕ

синтаксический анализ + перебор

Анализ алгоритма

Входная формула содержит не более 5 переменных, поэтому представляется возможным перебрать все возможные их значения. Переменные имеют булевый тип, поэтому принимают два значения: 0 (ложь) и 1 (истина). Формула имеет префиксную запись, поэтому ее значение легко может быть вычислено для заданного набора значений переменных. Если при вычислении формула для всех возможных входных значений переменных принимает истинное значение, то она является тавтологией.

Реализация алгоритма

В массиве m храним входную строку. В переменных p, q, r, s, t содержатся текущие значения терминальных символов.

char m[101];

int p, q, r, s, t;

Функция eval вычисляет значение формулы, содержащейся в массиве m. Значения терминальных символов, задействованных в формуле, содержатся в переменных p, q, r, s, t.

int eval(void)

{

int a, b;

if (m[ptr] == 'p') {ptr++; return p;}

if (m[ptr] == 'q') {ptr++; return q;}

if (m[ptr] == 'r') {ptr++; return r;}

if (m[ptr] == 's') {ptr++; return s;}

if (m[ptr] == 't') {ptr++; return t;}

if (m[ptr] == 'N') {ptr++; return 1-eval();}

if (m[ptr] == 'A')

{

ptr++;

a = eval(); b = eval();

return a || b;

}

if (m[ptr] == 'K')

{

ptr++;

a = eval(); b = eval();

return a && b;

}

if (m[ptr] == 'C')

{

ptr++;

a = eval(); b = eval();

return !a || b;

}

if (m[ptr] == 'E')

{

ptr++;

a = eval(); b = eval();

return a == b;

}

return 0;

}

Основной цикл программы. Читаем входную строку в массив m. Совершаем перебор значений пяти переменных p, q, r, s, t. Если хотя бы на одном наборе переменных значение формулы равно 0, то устанавливаем flag = 0, выходим из перебора и выводим “not”. Иначе сообщаем о том, что текущая проверяемая формула является тавтологией.

while(gets(m))

{

if (m[0] == '0') break;

flag = 1;

for(p = 0; p <= 1; p++) if (flag)

for(q = 0; q <= 1; q++) if (flag)

for(r = 0; r <= 1; r++) if (flag)

for(s = 0; s <= 1; s++) if (flag)

for(t = 0; t <= 1; t++)

{

ptr = 0; res = eval();

if (res == 0) { flag = 0;break; }

}

if (flag) printf("tautology\n");

else printf("not\n");

}